# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        mid_list, now_note = [], head
        while now_note:
            mid_list.append(now_note)
            now_note = now_note.next
        i, now_note, length = 1, head, len(mid_list)
        while i <= length / 2:
            now_note.next = mid_list[-i]
            now_note = now_note.next
            if i != length - i:
                now_note.next = mid_list[i]
            else:
                now_note.next = None
            now_note = now_note.next
            i += 1
        now_note.next = None


b = [ListNode(1), ListNode(2), ListNode(3), ListNode(4), ListNode(5)]
b[0].next = b[1]
b[1].next = b[2]
b[2].next = b[3]
b[3].next = b[4]
a = Solution()
a.reorderList(b[0])
for note in b:
    print(note.next.val)